package test;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author sunzhuokun
 * @date 14:39 2024/5/11
 * @description 贪吃蛇
 * 贪吃蛇是一个经典游戏，蛇的身体由若干方格连接而成，身体随蛇头移动。蛇头触碰到食物时，蛇的长度会增加一格。蛇头和身体的任一方格或者游戏版图边界碰撞时，游戏结束。
 * 下面让我们来完成贪吃蛇游戏的模拟：
 * 给定一个NM的数组ar，代表NM个方格组成的版图，贪吃蛇每次移动一个方格。若ar[i][j]=='H'，表示该方可为贪吃蛇的起始位置;若ar[i][j]=='F'，
 * 表示该方格为食物，若ar[i][j]=='E'，表示该方格为空格。
 * 贪吃蛇初始长度为1，初始移动方向为向左。输入为给定一系列贪吃蛇的移动操作，返回操作后蛇的长度，如果在操作执行完之前已经游戏结束，返回游戏结束时贪吃蛇的长度。
 * <p>
 * 输入描述: 输入第 1行为空格分隔的字母，代表贪吃蛇的移动操作。字母取值为 U、D、L、R、G，其中U、D、L、R分别表示贪吃蛇往上、下、左、右转向，
 * 转向时贪吃蛇不移动，G表示贪吃蛇按 当前的方向移动一格。用例保证输入的操作正确。
 * 第 2行为空格分隔的两个数，指定为 N和 M，为数组的行和列数。余下 N行每行是空格分 隔的 M个字母。字母取值为 H、F和 E，H表示贪吃蛇的起始位置，
 * F表示食物，E表示该 方格为空。用例保证有且只有一个 H，而 F和 E会有多个。
 * <p>
 * 输出描述:
 * 输出一个数字为蛇的长度。
 * <p>
 * 示 例:
 * 输入
 * DGG
 * 33
 * FFF
 * FFH
 * EFE
 * 输出
 * 1
 */
public class GreedySnake_贪吃蛇 {

    /**
     * DGLGGUGGRGGDGLG
     * 33
     * FFF
     * FFH
     * EFE
     *
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String operators = sc.nextLine();
        int rowAndCol = sc.nextInt();
        sc.nextLine();
        int row = rowAndCol / 10;
        int col = rowAndCol % 10;
        String[][] board = new String[row][col];
        List<Path> snake = new ArrayList<>();
        // 先构建地图，找到蛇头
        for (int i = 0; i < board.length; i++) {
            String line = sc.nextLine();
            for (int j = 0; j < board[0].length; j++) {
                if ("H".equals(line.substring(j, j + 1))) {
                    snake.add(new Path(i, j, "L"));
                }
                board[i][j] = line.substring(j, j + 1);
            }
        }

        // 遍历操作数，记录蛇头位置
        for (int i = 0; i < operators.length(); i++) {
            char operator = operators.charAt(i);
            switch (operator) {
                case 'U':
                    snake.get(0).setDirection("U");
                    break;
                case 'D':
                    snake.get(0).setDirection("D");
                    break;
                case 'L':
                    snake.get(0).setDirection("L");
                    break;
                case 'R':
                    snake.get(0).setDirection("R");
                    break;
                // 遇到G，移动
                default:
                    move(board, snake);
            }
        }
    }

    private static void move(String[][] board, List<Path> snake) {
        Path head = snake.get(0);
        String direction = head.getDirection();
        int row = 0;
        int col = 0;
        switch (direction) {
            case "U":
                row = head.getRow() - 1;
                col = head.getCol();
                break;
            case "D":
                row = head.getRow() + 1;
                col = head.getCol();
                break;
            case "L":
                row = head.getRow();
                col = head.getCol() - 1;
                break;
            default:
                row = head.getRow();
                col = head.getCol() + 1;
        }

        // 判断移动后，蛇头是否越界
        if (row > board.length - 1 || col > board[0].length - 1 || row < 0 || col < 0) {
            System.out.println(snake.size());
            return;
        }

        // 判断当前蛇头是否走到蛇神上
        for (int i = 1; i < snake.size() - 1; i++) {
            if (row == snake.get(i).getRow() && col == snake.get(i).getCol()) {
                System.out.println(snake.size());
                return;
            }
        }

        // 碰到食物，结束
        if (board[row][col].equals("F")) {
            snake.add(0, new Path(row, col, direction));
            System.out.println(snake.size());
            return;
        }

        // 正常运动
        snake.add(0, new Path(row, col, direction));
        snake.remove(snake.size() - 1);
    }

    static class Path {

        private int row;
        private int col;
        private String direction;

        public Path(int row, int col, String direction) {
            this.row = row;
            this.col = col;
            this.direction = direction;
        }


        public int getRow() {
            return row;
        }


        public int getCol() {
            return col;
        }


        public String getDirection() {
            return direction;
        }


        public void setDirection(String direction) {
            this.direction = direction;
        }


        public void setRow(int row) {
            this.row = row;
        }


        public void setCol(int col) {
            this.col = col;
        }
    }
}
